/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package edu.tue.nl.aa;

import java.util.ArrayList;
import java.util.Random;

/**
 *
 * @author waldo
 */
public class RandomizedQuickSort {

    private static final Random r = new Random();
    private static boolean io;

    /**
     * 
     * @param <E> , type of element. It should implement Comparable<E>.
     * @param s , data to sort
     * @param increasingOrder , 'true' to use increasing order, otherwise decreased order is used.
     * @return sorted data
     */
    public static <E extends Comparable<? super E>> ArrayList<E> sort(ArrayList<E> s, boolean increasingOrder){
        ArrayList<E> sorted = new ArrayList<E>();
        io = increasingOrder;
        rqs(s, sorted);
        return sorted;
    }
 
    /**
     * 
     * @param s
     * @param sorted 
     */
    private static <E extends Comparable<? super E>> void rqs(ArrayList<E> s, ArrayList<E> sorted){
        if(s.isEmpty()) return;
        if(s.size() == 1){
            sorted.add(s.get(0));
            return;
        }
        ArrayList<E> se = new ArrayList<E>(),
                sl = new ArrayList<E>(),
                sh = new ArrayList<E>();
        // get random xpiv
        E xpiv = s.get( r.nextInt(s.size()) );
        for( E next : s ){
            int compare = xpiv.compareTo(next);
            if( io ){
                if(compare < 0) sl.add(next); 
                else if(compare > 0) sh.add(next); 
                else se.add(next); 
            } else {
                if(compare > 0) sl.add(next); 
                else if(compare < 0) sh.add(next); 
                else se.add(next);
            }
        }
        rqs(sl, sorted);
        sorted.addAll(se);
        rqs(sh, sorted);
    }

    
}
